package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import LeetCode.interview._141_Linked_List_Cycle.ListNode;

import util.LogUtils;

/*
 * 
原题

　　Write a program to find the node at which the intersection of two singly linked lists begins. 
　　For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
　　begin to intersect at node c1. 
　　Notes: 
　　If the two linked lists have no intersection at all, return null. 
　　The linked lists must retain their original structure after the function returns. 
　　You may assume there are no cycles anywhere in the entire linked structure. 
　　Your code should preferably run in O(n) time and use only O(1) memory. 

题目大意
	
	前提 ：题目说明有共同元素
		两个指针一起遍历，相同速度，遇到 相同则为起点
			假如两个链表长度不同，则长的链表先遍历  两条链表的差值个节点
解题思路

 * @Date 2017-09-27 17：06
 */
public class _160_Intersection_of_Two_Linked_Lists {
    /** initialize your data structure here. */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    	int lenA = getListLength(headA), lenB = getListLength(headB);
    	int diff = Math.abs(lenA - lenB);
    	if (lenA > lenB) {
    		while (lenA > lenB) {
    			headA = headA.next;
    			lenA--;
    		}
    	} else {
    		while (lenA < lenB) {
       			headB = headB.next;
    			lenB--;
    		}
    	}
    	while (headA != null) {
    		if (headA == headB) {
    			return headA;
    		}
    		headA = headA.next;
    		headB = headB.next;
    	}
    	return null;
    }
    
    /**
     * 得到 链表长度
     * @param head
     * @return
     */
    private int getListLength(ListNode head) {
    	ListNode p = head;
    	int total = 0;
    	while (p != null) {
    		total ++;
    		LogUtils.print("____"+p.val);
    		p = p.next;
    	}
    	LogUtils.br();
    	return total;
    }

	public static void main(String[] args) {
		_160_Intersection_of_Two_Linked_Lists obj = new _160_Intersection_of_Two_Linked_Lists();
		obj.getIntersectionNode(null, null);
	}

}
